/**
 * ts工具类
 */


//优先队列
class PriorityQueue<T>{
    private arr:T[] = []
    constructor(private cmp:(parent:T,child:T)=>number){
    }   

    //向队列增加元素
    add(e:T){
        //0位置没有元素的时候,加个0,方便push
        if(this.length()<0) this.arr.push(e)
        this.arr.push(e)
        this.justifyFromBottom()
    } 

    //获取第一个元素
    peek():T|undefined{
        return this.isEmpty() ?  undefined : this.arr[1]
    }

    //删除队列的第一个元素并返回
    poll():T|undefined{
        if(this.isEmpty()) return undefined
        const top = this.arr[1]
        this.arr[1] = this.arr[this.arr.length-1]
        this.arr.pop()
        this.justifyFromTop(1)
        return top
    }

    //返回队列的长度（不包括arr[0]）
    length():number{
        return this.arr.length-1
    }

    isEmpty():boolean{
        return this.length() <= 0
    }

    //从最后向前调整
    private justifyFromBottom(){
        let cur = this.arr.length-1
        while(cur>1){
            let parent = Math.floor(cur/2)
            if(this.cmp(this.arr[parent],this.arr[cur])>0){
                //需要调整
                [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]]
                cur = parent
            }else{
                break
            }
        }
    }

    //从前向后调整
    private justifyFromTop(from:number){
        let left = from*2
        let right = left+1
        //判断存在孩子吗
        if(left>=this.arr.length) return
        let larger  = left
        //找到left和right更 “大”的那个
        if(right<this.arr.length&&this.cmp(this.arr[left],this.arr[right])>0){
            larger = right
        }
        //把更“大的”那个和父亲比较，调整
        if(this.cmp(this.arr[from],this.arr[larger])>0){
            [this.arr[from],this.arr[larger]] = [this.arr[larger],this.arr[from]]
            this.justifyFromTop(larger)
        }
    }
}

export {PriorityQueue}
